package ljl.codetop300;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 和 210 一样，但是比那个简单，先照猫画虎来一发
 *
 * 生成图时，"谁依赖它" 有用，"它依赖谁" 好像不是那么有用，反正两个解法都没用到 "它依赖谁"
 */
public class _207_can_finish {

  static class my_bfs {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
      int[] indegrees = new int[numCourses];
      List<List<Integer>> graph = new ArrayList<>();
      Queue<Integer> q = new LinkedList<>();
      for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
      }
      for (int[] each : prerequisites) {
        graph.get(each[1]).add(each[0]);
        indegrees[each[0]]++;
      }
      for (int i = 0; i < indegrees.length; i++) {
        if (indegrees[i] == 0) {
          q.offer(i);
        }
      }
      while (!q.isEmpty()) {
        int course = q.poll();
        numCourses--;
        for (int dependent : graph.get(course)) {
          if (--indegrees[dependent] == 0) {
            q.offer(dependent);
          }
        }
      }
      return numCourses == 0;
    }
  }

  static class my_dfs {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
      List<List<Integer>> graph = new ArrayList<>();
      int[] visited = new int[numCourses];
      for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
      }
      for (int[] pair : prerequisites) {
        graph.get(pair[1]).add(pair[0]);
      }
      for (int i = 0; i < numCourses; i++) {
        if (visited[i] == 0) {
          if (!dfs(i, visited, graph)) {
            return false;
          }
        }
      }
      return true;
    }
    boolean dfs(int i, int[] visited, List<List<Integer>> graph) {
      visited[i] = 1;
      for (int child : graph.get(i)) {
        if (visited[child] == 1) {
          return false;
        }
        if (visited[child] == 0) {
          if (!dfs(child, visited, graph)) {
            return false;
          }
        }
      }
      visited[i] = 2;
      return true;
    }
  }

  public static void main(String[] args) {
    boolean res = new my_dfs().canFinish(2, new int[][]{{1, 0}, {0, 1}});
    System.out.println(res);
  }
}
